package com.rom.sort;

import com.rom.Utils.Random;

import java.util.Arrays;
import java.util.Date;

public class ShellSort {

    public static void main(String[] args) {

//        int arr[] = {1,-2,3,-4,5};
        int arr[] = new int[300000];
        System.out.println(new Date());
        for (int i = 0; i < 300000; i++) {
            arr[i] = Random.random80000();
        }
        shellSort2(arr);
        System.out.println(new Date());
//        System.out.println(Arrays.toString(arr));
    }
    //移位法
    public static void shellSort2(int[] arr){
//        int temp;
        int index = 0;
        for (int gap = arr.length/2;gap> 0 ; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int insertVal = arr[i];  //当前的值
                int insertIndex = i;
                while (insertIndex-gap>=0 && insertVal < arr[insertIndex-gap]){
                    index++;
                    arr[insertIndex] = arr[insertIndex-gap];
                    arr[insertIndex-gap] = insertVal;
                    insertIndex -= gap;
                }
            }
        }
        System.out.println(index);
//        System.out.println("第一轮："+Arrays.toString(arr));
//        for (int i = 2; i < arr.length; i++) {
//            for (int j = i-2; j>=0; j-=2) {
//                if(arr[j]>arr[j+2]){
//                    temp = arr[j];
//                    arr[j] = arr[j+2];
//                    arr[j+2] = temp;
//                }
//            }
//        }
//        System.out.println("第二轮："+Arrays.toString(arr));
//        for (int i = 1; i < arr.length; i++) {
//            for (int j = i-1; j>=0; j-=1) {
//                if(arr[j]>arr[j+1]){
//                    temp = arr[j];
//                    arr[j] = arr[j+1];
//                    arr[j+1] = temp;
//                }
//            }
//        }
//        System.out.println("第三轮："+Arrays.toString(arr));
    }
    //交换法
    public static void shellSort(int[] arr){
        int temp;
        for (int gap = arr.length/2;gap> 0 ; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i-gap; j>=0; j-=gap) {
                    if(arr[j]>arr[j+gap]){
                        temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;
                    }
                }
            }
        }
    }
}
